Embodiments of the present invention relate generally to data representation, and more particularly to solving constraint problems using efficient methods and systems for representing variable domains.
Constraint programming is a discipline that deals with the representation of a problem in a manner that allows for solutions to be formulated. Each variable in a constraint problem may be modeled as a solution space comprising a range of discrete or continuous values. The relations and limitations between these variables may be expressed as constraints. The constraints act to limit the values in a variable's solution space. A solution is a state in which each variable has had its domain limited to a single value without violating any of the constraints. Often, software programs known as constraint solvers may be used to find one or more solutions to a given constraint problem, or alternatively, to prove that no solution exists.
Computer systems may use a method for solving constraint problems known as Arc Consistency. Arc Consistency ensures that every value in the domain of each variable has a supporting value in the other variables that satisfies all of the constraints. Values that are not consistent may be removed from the domain of each variable. The inference power of Arc Consistency ensures that every value of a variable is consistent with its constrained neighbor variables, thus eliminating inconsistent values from each solution.
For a computer system to efficiently perform the key functionality of reasoning over valid values and eliminating invalid values, the computer system must be able to efficiently represent to the domains of each variable. Existing methods for representing variable domains are limited. Hence, there is a need for improved methods and systems for efficiently representing data for solving constraint problems.